﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Spanner
{
    public class AList<K, V>
    {
        public K Key;
        public V Value;
        public AList<K, V> Tail;

        public static AList<K, V> Cons(K key, V value, AList<K, V> tail)
        {
            return new AList<K, V> { Key = key, Value = value, Tail = tail };
        }

        public static V LookupFirst(AList<K, V> aList, K key)
        {
            while (true)
            {
                if (aList == null) throw new KeyNotFoundException();
                if (object.ReferenceEquals(aList.Key, key)) return aList.Value;
                aList = aList.Tail;
            }
        }

        public static IEnumerable<V> LookupAll(AList<K, V> aList, K key)
        {
            while (aList != null)
            {
                if (object.ReferenceEquals(aList.Key, key)) yield return aList.Value;
                aList = aList.Tail;
            }
        }

        public static IEnumerable<KeyValuePair<K, V>> Firsts(AList<K, V> aList)
        {
            var seen = new HashSet<K> { };
            for (; aList != null; aList = aList.Tail)
            {
                var key = aList.Key;
                if (seen.Contains(key)) continue;
                yield return new KeyValuePair<K, V>(key, aList.Value);
                seen.Add(key);
            }
        }

        public static IEnumerable<KeyValuePair<K, List<V>>> Alls(AList<K, V> aList)
        {
            var seen = new HashSet<K> { };
            for (; aList != null; aList = aList.Tail)
            {
                var key = aList.Key;
                if (seen.Contains(key)) continue;
                yield return new KeyValuePair<K, List<V>>(key, LookupAll(aList, key).ToList());
                seen.Add(key);
            }
        }
    }
}
